#ifndef __CLIPPING_H__
#define __CLIPPING_H__
#include <string>
#include <vector>
using namespace std;

/*
* 分割问题, 类似于组合
* 
* 例如: 求 abcdef 所有的分割结果
* 可以类似于组合操作:
* a|bcedf ab|cdef a|b|cdef ....
* 可以看到分割的操作和组合中选取元素的操作大致相同(选 a-> 选b、从bcdef中选b)
* 其实可以看作是在选择元素时, 元素之间的区间组成了一个子串
*/
/*
* 回文字符串: 正读反读结果一致
* 
* 例: aab 的回文子串
* 在上述例子中, 回文子串包括: a、a、b、aa
* 
* 这里画一下树形结构:
*		            aab
*       a|ab           aa|b      aab|
*  a|a|b   a|ab|       aa|b|
* a|a|b|
* 
* 如上述的树形结构:
* 1.先切割 a, 得到 a ab 两个子串, 然后从 ab 中切割 a, 得到 a a b 子串, 最后从 b 中切割, 得到 a a b 子串
*                                   从 ab 中切割 b, 得到 a ab 子串
* 2.切割第二个 a, 得到 aa b 子串(切割 b 就不写了)
* 3.切割 b, 得到 aab 子串
* 
* 可以看到, 字符串 aab 所有的 子串的分割方案 都在树形结构的叶子节点中 
* 注意: 收集所有的叶子节点, 结果会有重复, 这里特指分割方案, 没有考虑去重。
* 
* 深度表示为分割线的个数, 广度表示为最深一层分割线的位移
*/

/*
* 注意: 这里返回的是分割方案
* 不限制分割次数, 得到所有的分割结果
*/
void BackingTrackingClipping(const string& str, vector<string>& path, vector<vector<string>>& results, int startIndex = 0) {
	if (startIndex == str.size()) {
		results.push_back(path);
		return;
	}

	for (int i = startIndex; i < str.size(); i++) {
		//子串 : [startIndex, i]
		path.push_back(str.substr(startIndex, i - startIndex + 1));
		BackingTrackingClipping(str, path, results, i + 1);
		path.pop_back();
	}
}

/*
* leetcode 131
* 分割回文子串 Palindrome (分割方案)
*/
bool IsPalindrome(const string& str, int startIndex, int endIndex) {
	for (int i = startIndex, j = endIndex; i < j; i++, j--) {
		if (str[i] != str[j])
			return false;
	}

	return true;
}

void BackingTrackingPalindrome(const string& str, vector<string>& path, vector<vector<string>>& results, int startIndex = 0) {
	if (startIndex == str.size()) {
		results.push_back(path);
		return;
	}

	for (int i = startIndex; i < str.size(); i++) {
		//子串 : [startIndex, i]
		if (IsPalindrome(str, startIndex, i))
			path.push_back(str.substr(startIndex, i - startIndex + 1));

		else	//不要疑惑, 确实是可以直接continue的, 起到一个剪枝的效果
			continue;

		BackingTrackingPalindrome(str, path, results, i + 1);
		path.pop_back();
	}
}

/*
* leetcode 93
* 复原 ip 地址
* 给出一串数字的字符串, 要求切割成合法的 ip 地址 (数字首位不为 0)
*
* 例如: 25525511135
* 结果: 255.255.11.135 ...
*
* 不合法: 01.011.255.245 (数字首位不为 0)
*		2555.55.11.135 (超过 255)
*/

/*
* 这种情况适用于限制分割次数
* 和组合问题不同, 分割的结果集可以组合成原始集合; 而组合问题是一个选择, 结果集不一定能组合成原始集合
*/
bool IsValid(const string& str);

/*
* 计算分割方案, 得到最终结果
*/
void BackTrackingIpAddress(const string& str, vector<string>& path, vector<vector<string>>& results, int clipTimes = 0, int startIndex = 0) {
	if (path.size() == 4 && IsValid(*(path.end() - 1))) {
		results.push_back(path);
		return;
	}

	for (int i = startIndex; i < str.size(); i++) {
		string subStr;

		//切割次数为 3, 则取末尾部分, 并且不进行循环 (不需要分割线后移)
		if (clipTimes == 3) {
			subStr = str.substr(i, str.size() - i);
			i = str.size();
		}
			
		else
			subStr = str.substr(startIndex, i - startIndex + 1);

		if (!IsValid(subStr))
			break;
			
		path.push_back(subStr);
		clipTimes++;
		BackTrackingIpAddress(str, path, results, clipTimes, i + 1);
		path.pop_back();
		clipTimes--;
	}
}

/*
* 添加分割线, 修改原始字符串, 得到最终结果
*/
void BackTrackingIpAddress(string& str, vector<string>& results, int clipTimes = 0, int startIndex = 0) {
	if (clipTimes == 3 && IsValid(str.substr(startIndex, str.size() - startIndex))) {
		results.push_back(str);
	}

	for (int i = startIndex; i < str.size(); i++) {
		if (!IsValid(str.substr(startIndex, i - startIndex + 1)))
			break;

		//添加分割线 '.'
		str.insert(str.begin() + i + 1, '.');
		clipTimes++;

		//需要注意迭代器失效问题
		BackTrackingIpAddress(str, results, clipTimes, i + 2);

		str.erase(str.begin() + i + 1);
		clipTimes--;
	}
}

bool IsValid(const string& str) {
	if (str.size() > 1 && str[0] == '0')
		return false;

	if (str.empty())
		return false;

	//out of range
	/*if (stoi(str) > 255)
		return false;*/

	int num = 0;
	int times = 1;
	for (string::const_reverse_iterator rbegin = str.rbegin(); rbegin != str.rend(); rbegin++) {
		if (*rbegin >= '0' && *rbegin <= '9') {
			num += (*rbegin - '0') * times;
			times *= 10;
		}

		else
			return false;

		if (num > 255)
			return false;
	}

	return true;
}

#endif // !__CLIPPING_H__

